A variety of systems are known in the art for providing drivers with in-vehicle electronic routing maps and navigation aids. These systems are commonly coupled to a location-finding device in the vehicle, such as a Global Positioning System (GPS) receiver, which automatically determines the current location of the vehicle, to be displayed on the map and used in determining routing instructions. The user typically inputs a desired destination, and navigation software then computes an optimal route between the route origin (typically, but not necessarily, the user's current location) and the destination, and provides route directions to the user in graphical and/or verbal format. The route computation may take place either “on board,” on the user's own mobile computing device, or “off board,” on a remote server, which communicates with the user's mobile device.
In many cases, a user may deviate from the route that was originally computed, either intentionally or unintentionally. Some types of navigation software are designed to deal with such deviations. For example, U.S. Patent Application Publication 2009/0125229, whose disclosure is incorporated herein by reference, describes a navigation system that computes an optimal route between an origin and a destination using a map server. The map server identifies likely points of deviation from the optimal route, and prior to transmitting map data to a client device, establishes alternative optimal routes from the deviations to the destination. A route corridor map including the optimal route and alternative routes is download from the map server to the client device.
As part of the routing process, points of interest (POIs) may be identified along the route. For example, U.S. Patent Application Publication 2011/0106429 describes a system in which a routing engine identifies POIs in a database located within a threshold distance from the planned route in Euclidean distance. The routing engine filters the results by exploring the road network to determine whether each of the POIs is within the threshold distance of the route in driving distance. For those POIs reached in the exploration, the nearest point on the route and the distance to that point are known. Similar searches are performed based on driving time rather than distance.